#include<stdio.h>
#include<stdlib.h>
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (list1 == NULL)
        return list2;
    if (list2 == NULL)
        return list1;
    struct ListNode* newlist = list1;
    struct ListNode* new = newlist;
    struct ListNode* newhead1 = list1;
    struct ListNode* newhead2 = list2;
    struct ListNode* cur1 = NULL;
    struct ListNode* cur2 = NULL;
    while (newhead1 && newhead2)
    {
        if (cur1 == NULL)
        {
            if (newhead1->val > newhead2->val)
            {
                newlist = newhead2;
                new = newlist;
            }
        }
        else
        {
            struct ListNode* cur1 = newhead1->next;
            struct ListNode* cur2 = newhead2->next;
            if (newhead2->val <= newhead1->val)
            {
                newlist->next = newhead1;
                newhead2->next = cur1;
                newhead1 = cur1;
                newlist = newlist->next;
            }
            else
            {
                newlist->next = newhead2;
                newhead2->next = cur2;
                newlist = newlist->next;
            }
        }

    }
    if (newhead2)
        newlist->next = newhead2;
    if (newhead1)
        newlist->next = newhead1;
    return new;
}
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
int kthToLast(struct ListNode* head, int k) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (k--)
    {
        fast = fast->next;
    }
    while (fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow->val;
}
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
int kthToLast(struct ListNode* head, int k) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    // if(head == NULL)
    //     return NULL;
    while (k--)
    {
        // if(fast == NULL)
        //     return NULL;
        fast = fast->next;
    }
    while (fast != NULL)
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow->val;

}
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}